91. 解码方法

发表于 | 分类于 | 阅读次数：

链接：https://leetcode-cn.com/problems/triangle/

题目描述

一条包含字母 A-Z 的消息通过以下方式进行了编码：

1
2
3
4
'A' -> 1
'B' -> 2
...
'Z' -> 26

给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1:

1
2
3
4
5
6
7
8
输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。
示例 2:

输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

分析

本题是一个很明显的递归问题，每次取一个枝，进行递归。比如对于226来说，其递归结构如下：

1
2
3
4
5
6
7
8
9
==
2
2
6
==
26
==
22
6

递归过程可以参考下面：
Alt text

本题我们想用的是动态规划进行求解，递归结构式从前往后的，比如想求226的，那么它就依赖于22的解法和2的解法。这样我们就能将第i步的解转化成i-1和i-2的解的组合。

本题还需要注意的是不符合数字情况，比如016、106这种数字中包含了0的情况！

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def __init__(self):
        self.dp = None

    def numDecodings(self, s: str) -> int:
        if len(s) == 0:
            return 0
        self.dp = [0] * (len(s) + 1)
        # 注意dp[i]存的是s[0:i-1]的结果,也就是说错开一位了
        self.dp[0] = 1
        for i in range(1, len(s) + 1):
            # 226
            # 考虑当前位置的数字，如果不为0
            if s[i - 1] != '0':
                self.dp[i] = self.dp[i - 1]
            # 考虑当前数组和前一位组成的是否在1-26
            if i > 1 and s[i - 2] != '0' and 1 <= int(s[i - 2: i]) <= 26:
                self.dp[i] += self.dp[i - 2]
        return self.dp[len(s)]